package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //课程表II
        class Solution {
            public int[] findOrder(int n, int[][] p) {
                int[] in = new int[n];                 // 入度
                int[] result = new int[n];             // 结果序列
                Map<Integer, List<Integer>> edges = new HashMap<>(); // 邻接表：b -> [a1,a2...]

                // 1) 建图 + 入度统计（b -> a，表示先修 b 再修 a）
                for (int i = 0; i < p.length; i++) {
                    int a = p[i][0], b = p[i][1];
                    edges.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
                    in[a]++;
                }

                // 2) 入度为 0 的课程先入队
                Deque<Integer> q = new ArrayDeque<>();
                for (int i = 0; i < n; i++) {
                    if (in[i] == 0) q.offer(i);
                }

                // 3) Kahn：不断出队，写入结果，并“删除”出边（后继入度--）
                int index = 0;
                while (!q.isEmpty()) {
                    int cur = q.poll();
                    result[index++] = cur; // 出队即进入拓扑序
                    for (int next : edges.getOrDefault(cur, Collections.emptyList())) {
                        if (--in[next] == 0) q.offer(next);
                    }
                }

                // 4) 验环：若未处理满 n 个课程，说明存在环（无法完成）
                if (index != n) return new int[0];

                // 5) 返回任意一种合法拓扑序
                return result;
            }
        }

        //火星词典
        class Solution2{
            // 邻接表：字符 -> 它后面能直接到达的字符集合（有向边 u -> v）
            Map<Character, Set<Character>> edges = new HashMap<>();
            // 入度表：字符 -> 入度值
            Map<Character, Integer> in = new HashMap<>();
            // 非法标记：遇到 "abc" 在 "ab" 前面这种前缀非法顺序时置为 true
            boolean flag = false;

            public String alienOrder(String[] words) {
                // 1) 初始化所有出现过的字符：入度置 0，邻接表放空 Set，避免后续判空分支
                for (String w : words) {
                    for (int i = 0; i < w.length(); i++) {
                        char c = w.charAt(i);
                        in.putIfAbsent(c, 0);
                        edges.putIfAbsent(c, new HashSet<>());
                    }
                }

                // 2) 只比较相邻单词提取“首个不同字符”的约束边（更小且充分的边集）
                for (int i = 0; i + 1 < words.length; i++) {
                    add(words[i], words[i + 1]); // 在 add 里做前缀非法性判定与加边
                    if (flag) return "";         // 发现非法前缀，直接无解
                }

                // 3) Kahn 拓扑排序：从入度为 0 的字符开始层层“削边”
                Queue<Character> q = new LinkedList<>();
                for (char ch : in.keySet()) {
                    if (in.get(ch) == 0) q.offer(ch);
                }

                StringBuffer ret = new StringBuffer();
                while (!q.isEmpty()) {
                    char cur = q.poll();
                    ret.append(cur);

                    // 当前点可能没有出边；如果没有，edges.get(cur) 是空 Set（已在初始化阶段 putIfAbsent）
                    for (char nxt : edges.get(cur)) {
                        in.put(nxt, in.get(nxt) - 1); // 削去一条入边
                        if (in.get(nxt) == 0) q.offer(nxt);
                    }
                }

                // 4) 若存在环，说明最终拓扑序长度 < 节点总数（不同字符总数）
                return ret.length() == in.size() ? ret.toString() : "";
            }

            // 只基于相邻单词 si、sj 抽取一条“首个不同字符”的有向边 u -> v
            // 规则：
            // - 从左到右找到首个不同字符 c1 != c2，则 edges[c1].add(c2)，并给 c2 入度 +1（注意去重）
            // - 否则（前缀相同），如果 si 比 sj 更长（如 "abc" 在 "ab" 前），则非法，flag = true
            public void add(String si, String sj) {
                int n = Math.min(si.length(), sj.length());
                int i = 0;
                for (; i < n; i++) {
                    char c1 = si.charAt(i), c2 = sj.charAt(i);
                    if (c1 != c2) {
                        if(!edges.containsKey(c1)){
                            edges.put(c1, new HashSet<>());
                        }
                        // 去重加边：避免重复加同一条边导致入度被多次加 1
                        if (!edges.get(c1).contains(c2)) {
                            edges.get(c1).add(c2);
                            in.put(c2, in.get(c2) + 1);
                        }
                        return; // 抽到一条边即可返回；相邻单词只贡献第一处差异的约束
                    }
                }
                // 能走到这里说明前 n 位完全相同；若前者更长则非法（前缀顺序错误）
                if (si.length() > sj.length()) flag = true;
                // 否则相等或更短是合法的（不产生新边）
            }
        }
    }
}